package gold.enterprise;

import gold.vo.TreeNode;

import java.util.*;
import java.util.Queue;

public class Ziru {

    public void printByLayer(TreeNode root) {
        if (null == root) return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int curLayerSize = queue.size();
            for (int i = 0; i < curLayerSize; i++) {
                TreeNode cur = queue.poll();
                System.out.print(cur.val + " ");
                if (null != cur.left) queue.offer(cur.left);
                if (null != cur.right) queue.offer(cur.right);
            }

            System.out.print(";\n");
        }
    }

    public List<List<String>> getAllPermutation(List<String> input) {
        List<List<String>> res = new ArrayList<>();
        boolean[] visited = new boolean[input.size()];
        List<String> cur = new LinkedList<>();
        dfs(input, cur, visited, res);
        return res;
    }

    public void dfs(List<String> input, List<String> cur, boolean[] visited, List<List<String>> res) {
        if (cur.size() == input.size()) {
            res.add(copyList(cur));
            return;
        }

        for (int i = 0; i < input.size(); i++) {
            if (visited[i]) continue;
            visited[i] = true;
            cur.add(input.get(i));

            dfs(input, cur, visited, res);

            cur.remove(cur.size() - 1);
            visited[i] = false;
        }
    }

    public List<String> copyList(List<String> list) {
        List<String> copy = new ArrayList<>();
        for (String el : list) {
            copy.add(el);
        }
        return copy;
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.createTree("1,2,3,null,null,4");
        Ziru ziru = new Ziru();
//        ziru.printByLayer(root);

        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");

        System.out.println(ziru.getAllPermutation(list));
    }

}
